


# 实现方法1
'''
# 空间复杂度O(lg n)
class BSTIterator:
    # inorder: 中序遍历iterator
    # TODO : 实现其它order iterator

    def __init__(self, root):
        self.stack = []
        self._push(root)

    def _push(self, node):
        # 尽可能多的_push
        while node:
            self.stack.append(node)
            node = node.left

    def hasNext(self):
        return bool(self.stack)

    def next(self, ):
        node = self.stack.pop()
        self._push(node.right)
        return node
'''

# 实现方法2
'''
# 空间复杂度O(lg n)
# inorder: preorder遍历iterator
# TODO : 实现其它order iterator
class BSTIterator:
    INIT_STATE = 0
    LEFT_DONE  = 1

    def __init__(self, root):
        self.stack = []
        self._push(root)

    def _push(self, node, state=INIT_STATE):
        # 每次push一个
        if node:
            self.stack.append((node, state))

    def hasNext(self):
        return bool(self.stack)

    def next(self, ):
        node, state = self.stack.pop()
        if state == self.LEFT_DONE:
            ret = node
        else:
            assert state == self.INIT_STATE
            # loop push node + node's all left
            # 前面pop top node出来, 这里再push进去
            # 如果node没有left, 应该返回node(记得push node.right)
            while node.left:
                self._push(node, self.LEFT_DONE)
                node = node.left
            ret = node

        self._push(ret.right)

        return ret
'''
